class MagicSquareGenerator:

    def __init__(self, n: int):
        self.n = n

    @property
    def ms_sum(self):
        """幻和"""
        return self.n * (self.n ** 2 + 1) // 2

    def odd_magic_square(self, n: int, ms: list, sx: int, sy: int, num: int, quadrant=1):
        """
        奇数幻方生成器
        n 每个象限的阶数
        ms 单个象限的幻方
        sx sy x y坐标的初始值
        quadrant 象限数目 此处为了方便使用，
        分别定义 1(左上) 2(右下) 3(右上) 4(左下)四个顺序和象限
        根据不同的象限，那么最大数值为n * n * quadrant
        比如分为4个象限，每个象限三阶，那么最大值分别为
        3 * 3 * 1
        3 * 3 * 2
        3 * 3 * 3
        3 * 3 * 4
        奇数幻方会在单偶数幻方中使用，所以需要用ms参数而非在函数内定义ms
        """
        y, x = sy, sx + n // 2  # 初始化第一行中间坐标
        ms[y][x] = num  # 填充居中数字
        while num != n ** 2 * quadrant:
            num += 1  # 为了避免num在1的情况下取余n为1，那么num先递增
            if num % n == 1:  # 重排便在下格填
                y += 1
            else:
                x += 1
                y -= 1
                if y < sy:  # 上出框时往下放
                    y = sy + n - 1
                if x >= sx + n:
                    x = sx  # 右出框时往左放
            ms[y][x] = num

    def single_even(self, ms: list):
        """单偶数幻方生成
        方法：把n阶幻方分为四个象限，对每个象限分别做奇数幻方填充
           ^
        A  |  B
        ---|--->
        C  |  D
        具体算法参照图片 21 ~ 25.png
        """
        num = 1
        half_n = self.n // 2
        # 填充四个象限 注意下面的四个起始坐标
        for p, q in zip(((0, 0),  # 左上
                         (half_n, half_n),  # 右下
                         (half_n, 0),  # 右上
                         (0, half_n)),  # 左下
                        range(1, 5)):  # 象限标记
            self.odd_magic_square(half_n, ms, p[0], p[1], num, quadrant=q)  # 填充ms做初始化
            num = half_n ** 2 * q + 1
        k = (self.n - 2) // 4  # 获取k值
        """
        n k
        6  1
        10 2
        14 3
        18 4
        22 5
        26 6
        从n为6开始的单偶幻方，k依次递增1
        那么筛选需要调换的黄色(A象限部分区域)或蓝色(C象限部分区域)就比较容易
        A象限 [range(k)列] + [中间+k-1列]
        """
        # 遍历A C象限区域并交换
        for y in range(self.n // 2):
            for x in range(k):
                c = x + k if y == k else x  # 此处参考图片24.png
                ms[y][c], ms[y + half_n][c] = ms[y + half_n][c], ms[y][c]  # 与蓝色区域交换

        # 遍历B D象限区域并交换
        # 获取B D象限中间y坐标
        bdy = half_n + half_n // 2
        for y in range(self.n // 2):
            for x in range(bdy, bdy - k + 1, -1):
                ms[y][x], ms[y + half_n][x] = ms[y + half_n][x], ms[y][x]

    def double_even(self, ms: list):
        """
        双偶数幻方生成器
        参照1 ~ 2.png
        """
        num = 1
        corner_nums = []  # 保存对角线坐标
        for y in range(self.n):
            for x in range(self.n):
                if y == x or x + y == self.n - 1:  # 上下左右四个角对角线坐标
                    ms[y][x] = 1
                    corner_nums.append(num)
                # 四根小对角线
                # 根据对角线坐标的规律不难发现，之和及之差均为4的倍数
                elif (y + x + 1) % 4 == 0 or \
                        (x - y) % 4 == 0:
                    ms[y][x] = 1
                    corner_nums.append(num)
                else:
                    ms[y][x] = num
                num += 1
        # 自左向右、自下向上
        corner_nums.sort(reverse=True)
        # print(corner_nums)
        for y in range(self.n - 1, -1, -1):
            for x in range(self.n - 1, -1, -1):
                if ms[y][x] == 1:
                    ms[y][x] = corner_nums.pop()

    @property
    def magic_square(self):
        if self.n < 3 or self.n > 10000:
            return None
        ms = [[0] * self.n for _ in range(self.n)]
        if self.n % 2 != 0:  # 奇数阶幻方
            self.odd_magic_square(self.n, ms, 0, 0, 1, quadrant=1)
        elif self.n % 2 == 0 and self.n % 4 != 0:  # 单偶数幻方
            self.single_even(ms)
        elif self.n % 4 == 0:  # 双偶数幻方
            self.double_even(ms)
        return ms

    @property
    def magic_square_string(self):
        s = ""
        if self.magic_square:
            for row in self.magic_square:
                for num in row:
                    # *号的意义：*号为后面元组第一个参数，在于获取最大值数字的长度，保证对齐
                    s += "%*d" % (len(str(self.n ** 2)) + 1, num)
                s += "\n"
        return s

    def check(self):
        print('magic square sum: ', self.ms_sum)
        print('checking: ...')
        # check row
        for i in range(self.n):
            assert sum(self.magic_square[i]) == self.ms_sum
        # check column
        from functools import reduce
        for i in range(self.n):
            assert reduce(lambda x, y: x + y,
                          (self.magic_square[i][j] for j in range(self.n))) == self.ms_sum
        # 对角线检查
        assert reduce(lambda x, y: x + y,
                      (self.magic_square[y][x] for y, x in zip(range(self.n), range(self.n)))) == self.ms_sum
        assert reduce(lambda x, y: x + y,
                      (self.magic_square[y][x] for y, x in zip(range(-1, -self.n - 1, -1),
                                                               range(self.n)))) == self.ms_sum
        print('pass')


# test
if __name__ == "__main__":
    n = 11
    ms = MagicSquareGenerator(n)
    print(ms.magic_square_string)
    print(ms.magic_square)
    ms.check()
